#include"AlgBoruvka.h" 

/*!
\file AlgBoruvka.cpp
\brief Contains implementation of AlgBoruvka.
\ingroup Plugins
*/

AlgBoruvka::AlgBoruvka( Graph *g ):Algorithm(g){

}

AlgBoruvka::~AlgBoruvka(){

}

void AlgBoruvka::run(){
	//Begin with a connected graph G containing edges of distinct weights and an empty set of edges T.
	for( int i = 0; i < graph()->numNodes(); i++ ){
		containerAdd();
		container(i).push_back( (new ContainerElement)->setNode(graph()->node(i)) );
	}
	
	//While the vertices of G connected by T are disjoint
	while( containerCount() > 1 ){
		
		//Begin with an empty set of edges E
		QList<Edge> E;
		//For each component
		for( int i = 0; i < containerCount(); i++ ){
			
			//Begin with an empty set of edges S
			QList<Edge> S;
			//For each vertex in the component
			for( int j = 0; j < container(i).size(); j++ ){
				
				//Add the cheapest edge from the vertex in the component to another vertex in a disjoint component to S
				QList<Edge> from = graph()->edgesFrom( *container(i)[j]->node() );
				for( int k = 0; k < from.size(); k++ ){
					const Edge &e = from[k];
					if( containerContaining(e.from()) == containerContaining(e.to()) ){
						from.removeAt(k);
						k--;
					}
				}
				
				
				if( from.size() == 0 ){
					continue;
				}
				while( from.size() > 1 ){
					
					if( from[0].label().toInt() > from[1].label().toInt() )
						from.pop_front();
					else
						from.removeAt(1);
				}
				S.push_back(from[0]);
			}
			//Add the cheapest edge in S to E
			while( S.size() > 1 ){
				if( S[0].label().toInt() > S[1].label().toInt() )
					S.pop_front();
				else
					S.removeAt(1);
			}
			if(S.size() == 1)
				E.push_back(S[0]);
		}
		//Add the resulting set of edges E to T
		while( E.size() > 0 ){
			merge( containerContaining(E[0].from()), containerContaining(E[0].to()), E[0] );
			E.pop_front();
		}
	}
	
	for( int i = graph()->numEdges() - 1; i >= 0; i-- ){
		const Edge &e = graph()->edge(i);
		bool found = false;
		for( int j = 0; j < container(0).size() && !found; j++ ){
			found = container(0)[j]->edge() != 0 && *container(0)[j]->edge() == e;
		}
		if( !found )
			graph()->removeEdge(e);
	}
}


void AlgBoruvka::merge( int src, int dst, const Edge &e ){
	if( src == dst ){
		return;
	}
	if( src < dst )
		swap(src, dst);
	while( container(src).size() > 0 ){
		container(dst).push_back( container(src).takeAt(0) );
	}
	for( int i = 0; i < container(dst).size(); i++ ){
		if( container(dst)[i]->edge() == 0 ){
			container(dst)[i]->setEdge(e);
			break;
		}
	}
	
	while(true){
		if( container( containerCount()-1 ).size() == 0 )
			containerPop();
		else
			break;
	}
}

int AlgBoruvka::containerContaining( const Node &n ){
	for( int i = 0; i < containerCount(); i++ ){
		for( int j = 0; j < container(i).size(); j++ ){
			if( *container(i)[j]->node() == n )
				return i;
		}
	}
	return -1;
}

void AlgBoruvka::swap( int &a, int &b ){
	int c = a;
	a = b;
	b = c;
}